Sympy Combinatorics

Author

Patel Devarsh Dipeshkumar

Published

February 22, 2025

Sympy Combinatorics

SymPy is an open-source Python library for symbolic mathematics. It allows users to perform algebraic computations, solve equations, manipulate expressions, and work with calculus, linear algebra, and more.

Introduction to SymPy Combinatorics

SymPy’s Combinatorics module provides tools for working with partitions, permutations, and other discrete structures in mathematics. It is useful in combinatorial problems, group theory, and counting principles.

Installation Steps

Sympy could be installed with the help of pip which is Python Package Manager

1. Install Using pip
Open a terminal or command prompt and run: pip install sympy

pip install sympy

Requirement already satisfied: sympy in c:\users\hp\appdata\local\programs\python\python312\lib\site-packages (1.13.3)
Requirement already satisfied: mpmath<1.4,>=1.1.0 in c:\users\hp\appdata\local\programs\python\python312\lib\site-packages (from sympy) (1.3.0)
Note: you may need to restart the kernel to use updated packages.


[notice] A new release of pip is available: 24.0 -> 25.0.1
[notice] To update, run: python.exe -m pip install --upgrade pip

2. Verify Installation
After installation, open Python and type

import sympy
print(sympy.__version__)  # It should print the installed SymPy version

1.13.3

Topic 1:- Partition

In simple words, a partition is a set of disjoint sets whose union equals a given set.

Problem 1) Imagine a teacher has 6 students: {1, 2, 3, 4, 5, 6} and wants to divide them into study groups based on their subject preferences. Each student belongs to exactly one group.

Group 0 (Math Lovers) → {1, 2, 3};
Group 1 (Science Enthusiasts) → {4, 5};
Group 2 (History Buffs) → {6}

We can solve this problem easily by using “Partitions”. So for that first of all we need to learn some basic properties.

Properties of Partition

1. RGS

It returns the “restricted growth string” of the partition.
Explanation - The RGS is given as a list of numbers, L, where each number L[i] tells you which indices the i-th element belongs to.

from sympy.combinatorics import Partition              #Importing the Partition class from the sympy.combinatorics module.
Example_RGS = Partition([1,2,3],[8,9],[4,5],[6],[7])   #Defining a partition of a set containing the elements {1,2,3,4,5,6,7,8,9}.
print(Example_RGS.members)                             #Here ".members" returns a tuple of elements in sorted order.
print(Example_RGS.RGS)                                 #.RGS returns a tuple of indices, where each index tells us which block the corresponding element belongs to

(1, 2, 3, 4, 5, 6, 7, 8, 9)
(0, 0, 0, 1, 1, 2, 3, 4, 4)

Now we can easily answer the ‘Q1)’ by using this property.

study_groups = Partition([1, 2, 3], [4, 5], [6])
print("Partition:", study_groups.partition)
print("RGS Representation:", study_groups.RGS)

Partition: [[1, 2, 3], [4, 5], [6]]
RGS Representation: (0, 0, 0, 1, 1, 2)

From the Output we can conclude that Students {1,2,3} are in group 0. Students {4,5} are in group 1. Student {6} is in group 2.

2. Partition

It returns partition as a sorted list of lists.

Explanation - A Partition in SymPy divides a set into disjoint, non-empty subsets (blocks) whose union equals the original set. The .partition attribute returns these blocks as a list of lists, representing the partition structure.

from sympy.combinatorics import Partition
Example_Partition = Partition([4], [2, 5]).partition
print(Example_Partition)

[[2, 5], [4]]

3. Rank

It gets the rank of a partition.

Explanation - The .rank attribute of a Partition in SymPy gives a unique integer representing the partition’s position in the lexicographic ordering of all partitions of the same set.

from sympy.combinatorics import Partition
Example_Rank = Partition([1, 2], [3], [4, 5])
print(Example_Rank.rank)

4. Conjugate

It computes the conjugate partition of itself.

Explanation - In SymPy, the .conjugate of an IntegerPartition interchanges the rows and columns in its Ferrers diagram representation, transforming the partition into another valid partition.

from sympy.combinatorics.partitions import IntegerPartition
Example_Conjugate = IntegerPartition([6, 3, 3, 2, 1])
print(Example_Conjugate.conjugate)

[5, 4, 3, 1, 1, 1]

Topic 2:- Subsets

In simple words, it represents a basic subset object.

Explanation - There are two main ways to create subsets: binary enumeration and lexicographic enumeration. In SymPy, the Subset class needs two inputs: the first is the subset we start with, and the second is the larger set it comes from.

Some basic Examples of Subset

from sympy.combinatorics import Subset
a = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
print(a.next_binary().subset)

['b']

Properties of Subsets

1. Cardinality

It returns the number of all possible subsets.

Explanation - The .cardinality property in SymPy returns the total number of possible subsets of a given set. Since a set with n elements has (2^n) subsets, this property calculates and returns that value.

from sympy.combinatorics import Subset
Example_Cardinality = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
print(Example_Cardinality.cardinality)

2. Subset

It gets the subset represented by the current instance.

The .subset property in SymPy returns the current subset being considered. It simply gives the list of elements that form the subset within the given superset.

from sympy.combinatorics import Subset
Example_Subset = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
print(Example_Subset.subset)

['c', 'd']

3. Superset

It gets the superset of the subset.

Explanation - The .superset property in SymPy returns the original (universal) set from which subsets are created. It shows the complete set that contains all possible elements for forming subsets

from sympy.combinatorics import Subset
Example_Superset = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
print(Example_Superset.superset)

['a', 'b', 'c', 'd']

4. Size

It gets the size of the subset.

Explanation - The .size property in SymPy returns the number of elements in the current subset. It simply counts how many elements are present in the subset.

from sympy.combinatorics import Subset
Example_Size = Subset(['a', 'c', 'd'], ['a', 'b', 'c', 'd'])
print(Example_Size.size)

5. Superset Size

It returns the size of the superset.

Explanation - The .superset_size property in SymPy returns the number of elements in the superset. It simply gives the total count of elements in the original (universal) set from which subsets are formed.

from sympy.combinatorics import Subset
Example_Superset_size = Subset(['c', 'd'], ['a', 'b', 'c', 'd'])
print(Example_Superset_size.superset_size)

Topic 3:- Gray Code

A Gray code is a way of listing all possible subsets of a set so that each new subset differs from the previous one by adding or removing just one element. This helps in efficient subset generation and has applications in computing and statistics.

Properties of Gray Code

1. Current

It returns the currently referenced Gray code as a bit string.

Explanation - The .current attribute shows the Current Gray code value in the sequence, and if a starting value is given, it starts from that value instead of the default (000).

from sympy.combinatorics import GrayCode
Example_Current_1 = GrayCode(3, start='100').current
print(Example_Current_1)
from sympy.combinatorics import GrayCode
Example_Current_2 = GrayCode(3).current
print(Example_Current_2)

100
000

2. Property n

It returns the dimension of the Gray code.

Explanation - The .current attribute shows the Current Gray code value in the sequence, and if a starting value is given, it starts from that value instead of the default (000).

from sympy.combinatorics import GrayCode
Example_Dimension = GrayCode(5)
print(Example_Dimension.n)

3. Rank

It ranks the Gray code.

Explanation - A ranking algorithm finds the position of a combinatorial object in a list of all possible objects, based on a specific order.

from sympy.combinatorics import GrayCode
Example = GrayCode(3)
print(list(Example.generate_gray()))
Example_Rank_1 = GrayCode(3, start='100').rank
print("The Rank of '100' is:", Example_Rank_1)
Example_Rank_2 = GrayCode(3, start='111').rank
print("The Rank of '111' is:", Example_Rank_2)

['000', '001', '011', '010', '110', '111', '101', '100']
The Rank of '100' is: 7
The Rank of '111' is: 5

4. Selections

It returns the number of bit vectors in the Gray code.

Explanation - The .selections property tells us how many values exist in the Gray code sequence. For example in n-bit Gray code, this number is always 2^n.

from sympy.combinatorics import GrayCode
Example_Selections_1 = GrayCode(3)
print(Example_Selections_1.selections)
Example_Selections_2 = GrayCode(5)
print(Example_Selections_2.selections)

8
32

Topic 4:- Permutations

Permutation is an important subdivision of sympy.combinatorics, they are fundamental concepts in combinatorics, representing the various ways to arrange a set of elements where the order is significant. In SymPy, the Permutation class provides tools to create and manipulate these arrangements.

To define a permutation, you specify a list that indicates the new positions of elements. Let us understand this with an example: `Permutation([2, 0, 1])` rearranges elements such that the element at index 0 moves to index 2, the element at index 1 moves to index 0, and the element at index 2 moves to index 1.

from sympy.combinatorics import Permutation

p = Permutation([2, 0, 1]) # We define the permutation here

print("Permutation is:", p)

Permutation is: (0 2 1)

Explanation

In this cycle notation, (0 2 1) indicates that index 0 maps to index 2, index 2 maps to index 1, and index 1 maps back to index 0, forming a cycle.

How can we apply permuation to a List?

To apply this permutation to a list of elements [A, B, C]:


original_elements = ['A', 'B', 'C']

p = Permutation([2, 0, 1])

permuted_elements = [original_elements[i] for i in p.array_form] #here the function .array_form just gives us an array of the permutation p

print("Original List:", original_elements)           
print("Permuted List:", permuted_elements)

Original List: ['A', 'B', 'C']
Permuted List: ['C', 'A', 'B']

This code rearranges the list [‘A’, ‘B’, ‘C’] to [‘B’, ‘C’, ‘A’] based on the permutation [2,0,1] as:

The element at pos 0 maps to the index 1 , the element at pos 1 maps to the index 2 and the element at the pos 2 maps athe index 0.

How can we apply permuation to a List?

Permutations play a crucial role in cryptography, particularly in the design of encryption algorithms. By permuting bits or blocks of data, encryption schemes can obscure the original information, enhancing security.

Properties of Permutations

1. Identity Permutation

A permutation where all elements remain in their original positions.

from sympy.combinatorics import Permutation

# here we have an identity permutation of size 4
p = Permutation([0, 1, 2, 3])
print("Identity Permutation:", p)

Identity Permutation: (3)

In this example,each element maps with itself suggesting no change in the position of the element.

2. Inverse of Permutation

A permutation that, when composed with the original, yields the identity permutation.

from sympy.combinatorics import Permutation

#here we Define a permutation
p = Permutation([2, 0, 1])
# to Compute its inverse we do
p_inv = ~p
print("Permutation:", p)
print("Inverse Permutation:", p_inv)

Permutation: (0 2 1)
Inverse Permutation: (0 1 2)

Here,on applying p followed by its inverse p_inv returns elements to their original positions.

3. Order of Permutation

The smallest positive integer k such that applying the permutation k times results in the identity permutation.

from sympy.combinatorics import Permutation

#Here we Define a permutation
p = Permutation([1, 2, 0])
#To Compute its order we do
order = p.order()
print("Permutation:", p)
print("Order of the Permutation:", order)

Permutation: (0 1 2)
Order of the Permutation: 3

Applying this permutation 3 times (i.e the order) returns the set to its original configuration.

4. Parity of Permutation

Indicates whether a permutation is even or odd, based on the number of transpositions (pairwise swaps) required to achieve it.

from sympy.combinatorics import Permutation

#here we Define a permutation
p = Permutation([1, 0, 2])
#to check its parity we do
is_even = p.is_even
print("Permutation:", p)
print("Is the permutation even?", is_even)

Permutation: (2)(0 1)
Is the permutation even? False

As we can see this permutation is odd, as it can be achieved with a single transposition: swapping elements 0 and 1.

5. Cyclic Decomposition

Expressing a permutation as a product of disjoint cycles, where each cycle represents a subset of elements permuted among themselves.

from sympy.combinatorics import Permutation

#Here we Define a permutation
p = Permutation([2, 0, 1, 4, 5, 3])
#To Get its cyclic form we do
cycles = p.cyclic_form
print("Permutation:", p)
print("Cyclic Decomposition:", cycles)

Permutation: (0 2 1)(3 4 5)
Cyclic Decomposition: [[0, 2, 1], [3, 4, 5]]

This permutation consists of two disjoint cycles: one cycling elements 0, 2, and 1; the other cycling elements 3, 4, and 5.

Topic 5:- Permutation Groups

In SymPy, a permutation group is a collection of permutations (rearrangements) that follow group properties. It is represented using the PermutationGroup class in sympy.combinatorics.

How to create Permutation Group in SymPy?

So first step is to create permuations: A permutation is represented as a list where indices represent elements, and values represent their new positions after permutation

from sympy.combinatorics import Permutation, PermutationGroup

# Defining permutations
p1 = Permutation([1, 2, 0]) # -> (0 1 2)
p2 = Permutation([2, 0, 1]) # -> (0 2 1)

# Creating a group
G = PermutationGroup([p1, p2])

print("Permutation Group:", G)

Permutation Group: PermutationGroup([
    (0 1 2),
    (0 2 1)])

A permutation group consists of multiple permutations as shown above.

Properties of Permutation Group

1. Identity of a group

Every group must have an identity element that does nothing.

print("Identity Element of the Group:", G.identity)

Identity Element of the Group: (2)

This confirms that [0, 1, 2] is the identity permutation.

2. Order of the group

The order of a group is the total number of distinct elements it contains.

print("Order of the Group:", G.order())

Order of the Group: 3

The group has 3 unique permutations, thus the order is 3.

3. Finding group elements

The .generate() method lists all permutations in the group.

print("Elements of the Group:", list(G.generate()))

Elements of the Group: [Permutation(2), Permutation(0, 1, 2), Permutation(0, 2, 1)]

It suggests that the group consists of three distinct permutations.

4. Permutation Check

The .generate() method lists all permutations in the group.

p_test = Permutation([2, 1, 0])  
print("Is p_test in the Group?", p_test in G)

Is p_test in the Group? False

Beyond the topics discussed, SymPy provides several other powerful combinatorial tools, including:

Polyhedron – Represent and manipulate polyhedral structures.
Prufer Sequences – Encode labeled trees uniquely.
Named Groups – Access predefined mathematical groups.
Galois Groups – Study polynomial symmetries.
Number of Groups – Count groups of a given order.
Utilities – Helper functions for combinatorial tasks.
Group Constructors – Create groups from generators.
Test Utilities – Validate group properties.
Tensor Canonicalization – Standardize tensor expressions.
Finitely Presented Groups – Define groups with generators and relations.
Polycyclic Groups – Work with structured solvable groups.

To explore these topics in depth, refer to the official SymPy documentation :- https://docs.sympy.org/latest/modules/combinatorics/index.html

Use-Cases (Practical Application)

Example 1) Consider a Simple example where a basic encryption method is used to permute the position of characters according to a pre-defined scheme

message = "HELLO"

# Permutation pattern according to the indices
permuted_pattern = [4, 2, 0, 3, 1]  # This is a permutation of indices [0, 1, 2, 3, 4]

# Applying permutation to encrypt
encrypted_message = ''.join([message[i] for i in permuted_pattern])

print("Original Message:", message)          
print("Encrypted Message:", encrypted_message)

Original Message: HELLO
Encrypted Message: OLHLE

In this example, the original message “HELLO” is rearranged to “OLHLE” using the permutation pattern [4, 2, 0, 3, 1]. Decrypting the message would involve applying the inverse of this permutation to restore the original order.

So this is one of practical application of Permutation which is a part of Sympy Combinatorics

Example 2):-

Imagine a smart home system with 4 devices that can be turned ON or OFF:

Lights (‘L’)
Fan (‘F’)
TV (‘T’)
AC (‘A’)

A subset of these devices represents the currently active (ON) devices.

Now the problem is that we need to track which devices are ON at any moment and the system wants to automatically switch to the next possible combination of ON devices.

from sympy.combinatorics import Subset
all_devices = ['L', 'F', 'T', 'A']                   #First of all defining the all devices in a list in short form for ease.
current_on_devices = Subset(['T', 'A'], all_devices)   # Define the initial subset (devices that are ON)
next_on_devices = current_on_devices.next_binary().subset   # Get the next possible subset in binary order (next device combination)
print("All Devices:", all_devices)
print("Currently ON Devices:", current_on_devices.subset)
print("Next ON Device Combination:", next_on_devices)

All Devices: ['L', 'F', 'T', 'A']
Currently ON Devices: ['T', 'A']
Next ON Device Combination: ['F']

So this algorithm helps us to find the Devices which are currently ON and also gives the knowledge about the next device which is ON.

Example 3):-

Consider an intresting example in Chemistry & Molecular Symmetry

Molecules have symmetry groups, which help predict chemical reactions and stability.

Example: The benzene molecule (C₆H₆) follows D₆h symmetry, which is a permutation group.

This is how SymPy helps

benzene_rotation = Permutation([1, 2, 3, 4, 5, 0])  # Rotating atoms in benzene
G = PermutationGroup([benzene_rotation])
print("Symmetry Order of Benzene:", G.order())

Symmetry Order of Benzene: 6

Example 4):-

AI in chess engines like AlphaZero uses group-based search for move evaluations and this is how sympy helps

ai_move1 = Permutation([2, 0, 1])  # AI evaluating moves
ai_move2 = Permutation([1, 2, 0])
G = PermutationGroup([ai_move1, ai_move2])
print("AI Move Permutations:", list(G.generate()))

AI Move Permutations: [Permutation(2), Permutation(0, 1, 2), Permutation(0, 2, 1)]

References Used :- https://docs.sympy.org/latest/modules/combinatorics/index.html
https://en.wikipedia.org/wiki/SymPy
Finding practical applications - AI Tools used

Sympy Combinatorics

SymPy is an open-source Python library for symbolic mathematics. It allows users to perform algebraic computations, solve equations, manipulate expressions, and work with calculus, linear algebra, and more.

Introduction to SymPy Combinatorics

SymPy’s Combinatorics module provides tools for working with partitions, permutations, and other discrete structures in mathematics. It is useful in combinatorial problems, group theory, and counting principles.

Installation Steps

Sympy could be installed with the help of pip which is Python Package Manager

Topic 1:- Partition

In simple words, a partition is a set of disjoint sets whose union equals a given set.

Problem 1) Imagine a teacher has 6 students: {1, 2, 3, 4, 5, 6} and wants to divide them into study groups based on their subject preferences. Each student belongs to exactly one group. Group 0 (Math Lovers) → {1, 2, 3}; Group 1 (Science Enthusiasts) → {4, 5}; Group 2 (History Buffs) → {6}

We can solve this problem easily by using “Partitions”. So for that first of all we need to learn some basic properties.

Properties of Partition

1. RGS

2. Partition

3. Rank

4. Conjugate

Topic 2:- Subsets

In simple words, it represents a basic subset object.

Properties of Subsets

1. Cardinality

2. Subset

3. Superset

4. Size

5. Superset Size

Topic 3:- Gray Code

A Gray code is a way of listing all possible subsets of a set so that each new subset differs from the previous one by adding or removing just one element. This helps in efficient subset generation and has applications in computing and statistics.

Properties of Gray Code

1. Current

2. Property n

3. Rank

4. Selections

Topic 4:- Permutations

Permutation is an important subdivision of sympy.combinatorics, they are fundamental concepts in combinatorics, representing the various ways to arrange a set of elements where the order is significant. In SymPy, the Permutation class provides tools to create and manipulate these arrangements.

How can we apply permuation to a List?

How can we apply permuation to a List?

Properties of Permutations

1. Identity Permutation

2. Inverse of Permutation

3. Order of Permutation

4. Parity of Permutation

5. Cyclic Decomposition

Topic 5:- Permutation Groups

Properties of Permutation Group

1. Identity of a group

2. Order of the group

3. Finding group elements

4. Permutation Check

Use-Cases (Practical Application)

Example 2):-

Example 3):-

Example 4):-

Problem 1) Imagine a teacher has 6 students: {1, 2, 3, 4, 5, 6} and wants to divide them into study groups based on their subject preferences. Each student belongs to exactly one group.

Group 0 (Math Lovers) → {1, 2, 3};
Group 1 (Science Enthusiasts) → {4, 5};
Group 2 (History Buffs) → {6}